//
// Created by lxinp on 2022/8/29.
//

#ifndef DATASTRUCTURE_LRU_CACHE_H
#define DATASTRUCTURE_LRU_CACHE_H

#include <unordered_map>

using namespace std;


class LRUCache {
private:
    struct DoublyLinkedNode {
        int key, val;
        DoublyLinkedNode* prev;
        DoublyLinkedNode* next;
        DoublyLinkedNode() : key(0), val(0), prev(nullptr), next(nullptr) {}
        DoublyLinkedNode(int _key, int _val) : key(_key), val(_val), prev(nullptr), next(nullptr) {}
    };

    int size, capacity;
    DoublyLinkedNode* head;
    DoublyLinkedNode* tail;
    unordered_map<int, DoublyLinkedNode*> cache;

public:
    LRUCache(int _capacity) : size(0), capacity(_capacity) {
        head = new DoublyLinkedNode;
        tail = new DoublyLinkedNode;
        head->next = tail;
        tail->prev = head;
    }

    ~LRUCache() {
        while (size > 0) remove_from_tail();
        delete head;
        delete tail;
    }

    int get(int key) {
        if (!cache.count(key)) return -1;
        // The key exists, just find its position in hash table and move it to the head
        DoublyLinkedNode* node = cache[key];
        move_to_head(node);
        return node->val;
    }

    void put(int key, int value) {
        if (!cache.count(key)) {
            DoublyLinkedNode* node = new DoublyLinkedNode(key, value);
            cache[key] = node;
            add_to_head(node);
            size++;
            if (size > capacity) remove_from_tail();  // size-- inside
        } else { // The key exists, size unchanged
            DoublyLinkedNode* node = cache[key];
            node->val = value;
            move_to_head(node);
        }
    }

private:
    void add_to_head(DoublyLinkedNode* node) {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }

    void remove_node(DoublyLinkedNode* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void move_to_head(DoublyLinkedNode* node) {
        remove_node(node);
        add_to_head(node);
    }

    void remove_from_tail() {
        DoublyLinkedNode* removed = tail->prev;
        remove_node(removed);
        cache.erase(removed->key);  // This is why the Node should store key
        delete removed;
        size--;
    }
};


#endif //DATASTRUCTURE_LRU_CACHE_H
